/**
 * 寻找公共后缀的位置：
 * 假如采用带头结点的单链表保存单词，当两个单词有相同后缀时候，可以共享相同的后缀存储空间.
 * 例如:loading和being有相同的后缀ing
 * [l][o][a][d] 
 * 			  ->[i][n][g]
 * 		 [b][e]
 * 返回它们的公共后缀 
 */
#include <stdio.h>
#include <stdlib.h>

#define bool int
#define true !0
#define false 0

typedef struct LNode{
	char ch;
	struct LNode* next;
} LNode, *LinkedList; 

//获取当前链表的长度
int len(LinkedList &list)
{
	LinkedList node=list->next;
	int len=0;
	while(node->next)
	{
		len++;
		node=node->next;
	}
	return len;
}

LNode* core(LinkedList &L1, LinkedList &L2)
{
	int len_L1=len(L1);
	int len_L2=len(L2);
	LNode *p1=L1;	//p1为L1的遍历指针
	LNode *p2=L2; 	//p2为L2的遍历指针
	
	//如果L1的长度大于L2的长度，p1结点应该从第(m-n+1)个位置处开始和p2遍历
	for(p1=L1; len_L1 > len_L2; len_L1--) p1=p1->next;
	
	//如果L2的长度大于L1的长度，p2结点应该从第(n-m+1)个位置处开始和p1遍历
	for(p2=L2; len_L2 > len_L1; len_L2--) p2=p2->next;
	
	//p1和p2指针同时向后移动,当p1=p2是代表找到
	while(p1->next && p1->next!=p2->next)
	{
		p1=p1->next;
		p2=p2->next;
	}
	//返回公共后缀的起始位置
	return p1->next;
}